package Demo1;

public class Solution {
    public boolean isPalindrome(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    //1、找到链表的中间结点
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    //2、反转中间节点后面的链表
    ListNode cur = slow.next;
    while(cur != null){
        ListNode curNext = cur.next;
        cur.next = slow;
        slow = cur;
        cur = curNext;
    }
    //判断是否回文
    while(head != slow){
        if(head.val != slow.val){
            return false;
        }
        if(head.next == slow){
            return true;
        }
        head = head.next;
        slow = slow.next;
    }
    return true;
    }
    //两数相加（逆序）
    //1、将两个链表看成同等长度进行遍历，若一个链表较短就在前面补0
    //2、每一位计算之后要考虑上一位的进位问题，当前位计算结束也需要考虑更新进位值
    //3、两个链表遍历完后，若进位值为1，则在新链表最前放添加节点1
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode nH = new ListNode(0);
        ListNode cur = nH;
        int carry = 0;
        while(l1 != null || l2 != null){
            int x = 0;
            if(l1 != null){
                x = l1.val;
            }
            int y = 0;
            if(l2 != null){
                y = l2.val;
            }
            int sum = x + y + carry;
            carry = sum / 10;
            int val = sum % 10;
            cur.next = new ListNode(val);
            cur = cur.next;
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }
        if(carry == 1){
            cur.next = new ListNode(1);
        }
        return nH.next;
    }
    //删除倒数第n个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //判定链表中是否有元素
        if(head == null){
            return null;
        }
        //计算链表的长度
        ListNode cur = head;
        int size = 0;
        while(cur != null){
            cur = cur.next;
            size++;
        }
        //判定下标合法性
        if(n == 0 || n > size){
            return null;
        }
        //单独删除头节点，防止空指针异常
        if(n == size){
            if(head.next == null){
                return null;
            }
            head = head.next;
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        //找到倒数第n+1个节点
        //让fast先走n步
        while(n > 0){
            fast = fast.next;
            n--;
        }
        //注意这里是让fast走到最后一个元素
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        //删除元素
        slow.next = slow.next.next;
        return head;
    }
    //两两交换链表中的节点
        public ListNode swapPairs(ListNode head) {
            //创建哑节点
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;
            //每次需要交换tmp后面的两个节点，如果tmp后面只有1个或没有节点，则不需要交换
            ListNode tmp = dummyHead;
            while(tmp.next != null && tmp.next.next != null){
                ListNode n1 = tmp.next;
                ListNode n2 = tmp.next.next;
                //交换
                tmp.next = n2;
                n1.next = n2.next;
                n2.next = n1;
                tmp = n1;
            }
            return dummyHead.next;

    }
}



class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

